import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;

public class BinaryTree {
    static class TreeNode{
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
    //创建一颗二叉树
    public TreeNode CreatTreeNode(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        A.left = B;
        A.right = C;
        B.right = D;
        D.left = E;
        return A;//就是根节点
    }

    //前序遍历
    public void preTree(TreeNode root){
        if (root == null){
            return;
        }
        System.out.print(root.val + " ");
        preTree(root.left);
        preTree(root.right);
    }

    public void inorder(TreeNode root){
        if (root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val + " ");
        inorder(root.right);
    }

    public void postorder(TreeNode root){
        if (root == null){
            return;
        }
        postorder(root.left);
        postorder(root.right);
        System.out.print(root.val + " ");
    }

    //层序遍历
    public void levelorder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null){
            return;
        }
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size;i++){
                TreeNode node = queue.poll();
                System.out.print(node.val + " ");
                if (node.left != null){
                    queue.offer(node.left);
                }
                if (node.right != null){
                    queue.offer(node.right);
                }
            }
        }
    }

    //遍历
    public static int nodesize;
    public int size1(TreeNode root){
        if(root == null){
            return 0;
        }
        nodesize++;
        size1(root.left);
        size1(root.right);
        return nodesize;
    }

    //子问题
    public int size2(TreeNode root){
        if(root == null){
            return 0;
        }
        return size2(root.left) + size2(root.right) + 1;
    }

    //叶子结点
    public static int LeafSize;
    //遍历
    public int getLeafSize1(TreeNode root){
        if (root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            LeafSize++;
        }
        getLeafSize1(root.left);
        getLeafSize1(root.right);
        return LeafSize;
    }
    public int getLeafSize2(TreeNode root){
        if (root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        return getLeafSize2(root.left) +
                getLeafSize2(root.right);
    }

    //二叉树最大高度
    public int getHeight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight + 1
                : rightHeight + 1;
    }

    public static int ans = 0;
    public int getHeight1(TreeNode root){
        if(root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            ans++;
        }
        getHeight1(root.left);
        getHeight1(root.right);
        return ans;
    }

    //二叉树最小深度
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        if (root.left == null && root.right == null){
            return 1;
        }
        int min = Integer.MAX_VALUE;
        int leftHeight = minDepth(root.left);
        int rightHeight = minDepth(root.right);
        if(root.left != null){
            min = Math.min(leftHeight,min);
        }
        if(root.right != null){
            min = Math.min(rightHeight,min);
        }
        return min + 1;
    }
    //获取第K层的节点个数
    public int getLevelNodesize(TreeNode root,int k){
        if(root == null){
            return 0;
        }
        if (k == 1){
            return 1;
        }
        return getLevelNodesize(root.left,k-1) +
                getLevelNodesize(root.right,k-1);
    }
    //搜索查值
    public TreeNode Find(TreeNode root,char target){
        //先序遍历查询
        if (root == null){
            return null;
        }
        if(root.val == target){
            return root;
        }
        TreeNode left = Find(root.left,target);
        if (left != null){
            return left;
        }
        TreeNode right = Find(root.right,target);
        if (right != null){
            return right;
        }
        return null;
    }
    public boolean isCompelet(TreeNode root) {
        if (root == null) {
            return true;
        }
        //完全二叉树：连续，中间没有非空节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left == null) {
                    return false;
                }
                queue.offer(node.left);
                if (node.right == null) {
                    return false;
                }
                queue.offer(node.right);
            }
        }
        return true;
    }

    //非递归版遍历
    public void preorderNot(TreeNode root){

    }
}


